---
title: "9、李白打酒加强版"
created: 2025-11-28
tags:
  - 算法
---

# 9、李白打酒加强版

## 题目 [李白打酒加强版](https://www.lanqiao.cn/paper/3822/problem/2114/)

![[image-723f1a9b.png]]

## 思路分析

很明显是个dp问题

考虑怎么把状态表示清楚

![[image-69182c9a.png]]

状态表示： `f[i][j][k][c]` 遇见了i次店 j次花 手上有k斗酒 且此时是在c（店/花）的所有情况的集合
属性：count

状态转移：

若此时为花 c=0 即`f[i][j][k][0]` 因为遇花喝一斗 说明上一个状态应该是 第j-1次遇见花 然后手上应该有k+1斗酒
不确定的是上一步到底是花还是店 但是情况是两者的选择数之和 所以直接加就行了

`f[i][j][k][0]=f[i][j-1][k+1][0]+f[i][j-1][k+1][1];`

若此时为店 c=1 即f[i][j][k][1] 因为遇店翻一倍 说明 上一个状态应该是 第i-1次遇到店 然后手上有k/2斗酒 同理 两个情况加一下

`f[i][j][k][1]=f[i-1][j][k/2][0]+f[i-1][j][k/2][1];`

考虑一下这两种方式有什么限制（一定要合法）

首先考虑遇花（当前位置是花） 什么情况才能合法遇花 上一步k大于0的情况才能喝一斗 所以k+1>0 k>-1

然后考虑遇店（当前位置是店） 什么情况才能合法遇店 遇店翻一番 如果此时的k不能被一个合法的k/2乘得到 就不合法 换句话说 k/2要是整数
那么条件就是 k%2==0

接下来考虑初始化

初始可以看作是 经过了0个店 0个花 然后手上有2斗酒 此时为c(店或者花）这个无所谓 姑且当做是店吧 的情况有1种 所以`f[0][0][2][1]=1;` 其他情况都是0种
不用管 自动初始0

最后的答案应该是 经过n个店 m个花 然后手上有0斗酒 且当前在花（0)时的所有选法数

取出`f[n][m][0][0]`即可

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N=110,mod=1000000007;

int f[N][N][N][2];

int main()

{

	int n,m;

	cin>>n>>m;

	f[0][0][2][1]=1;

	for(int i=0;i<=n;i++){//店

		for(int j=0;j<=m;j++){//花

			for(int k=0;k<100;k++){//酒

				for(int c=0;c<2;c++){//当前位置

					if(j>0 && c==0 && k>-1)

						f[i][j][k][c]=(f[i][j-1][k+1][0]+f[i][j-1][k+1][1])%mod;

					if(i>0 && c==1 && k%2==0)

						f[i][j][k][c]=(f[i-1][j][k/2][0]+f[i-1][j][k/2][1])%mod;

				}

			}

		}

	}

	cout<<f[n][m][0][0];

	return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[8、扫雷|8、扫雷]] 🏠 [[00-刷题理模型]] ➡️ [[第十三届 c++ B组 省赛|第十三届 c++ B组 省赛]]